package binaryTree;

import java.util.*;

public class D230723 {
    // 创建二叉树
    // 双指针,递归
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        return dfs(0, 0, in.length - 1, pre, in);
    }
    public TreeNode dfs(int preStart, int inStart, int inEnd, int[] pre, int[] in) {
        if (preStart == pre.length || inStart > inEnd) {
            return null;
        }
        // 前序的第一个是根节点
        TreeNode root = new TreeNode(pre[preStart]);
        // 找根节点在中序中的位置，分割左右子树
        int index = 0;
        for (int i = inStart; inStart <= inEnd; i++) {
            if (pre[preStart] == in[i]) {
                index = i;
                break;
            }
        }

        root.left = dfs(preStart + 1, inStart, index - 1, pre, in);
        root.right = dfs(preStart + index - inStart + 1, index + 1, inEnd, pre, in);

        return root;
    }

    // 输出二叉树的右视图
    // 先重构二叉树
    // 然后层序遍历二叉树
    // 记录每层的最后一个节点
    public int[] solve (int[] preOrder, int[] inOrder) {
        if (preOrder.length == 0) {
            return null;
        }
        TreeNode root = dfs(0, 0, inOrder.length - 1, preOrder, inOrder);
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int deep = 0;
        while (!queue.isEmpty()) {
            int count = queue.size();
            for (int i = 0; i < count; i++) {
                root = queue.poll();
                if (i + 1 == count) {
                    list.add(root.val);
                }
                if (root.left != null) {
                    queue.add(root.left);
                }
                if (root.right != null) {
                    queue.add(root.right);
                }
            }
        }
        int[] ret = new int[list.size()];
        for (int i = 0; i < ret.length; i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}
